班级活动
题目 班级活动
思路分析
注意 题目是说 要成对出现 且同样的数存在两个 即否决了4 6 8这样的对
一开始没看到这一点 自以为是地用异或去写
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1e5+10;
unordered_map<int,bool> a;
int n;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
while(n--){
int x;cin>>x;
a[x]^=1;
}
int cnt=0;
for(auto x:a){
// cout<<x.first<<" "<<x.second<<endl;
if(x.second==1)
cnt++;
}
cout<<cnt/2;//cnt + divisor - 1 实现除以 divisor向上取整
return 0;
}
加上这点 每个只能两次的限制 问题其实就变成了贪心的平均数那块的模板
小于2的一定被补 大于2的一定补给小于2的 等于2的肯定不动 因为补给其他人到时候又要被补回来 走了无效的重复路
令id唯一的集合为A（只出现一次的元素） 必须修改的集合为B（出现两次以上的元素）
可分为两种情况
1、B≥A时
假设有一个 id 集合 A = { 1 , 2 , 3 , 4 , 4 , 4 , 4 , 5 , 5 , 5 , 5 , 5 }
此时 id 唯一的集合为 { 1 , 2 , 3 }
必须修改的 id 集合为 { 4 , 4 , 5 , 5 , 5 }
只需要让后一个集合的 id 分别修改为 { 1 , 2 , 3 , 6 , 6 } 即可符合要求
这种情况下 需要修改的数量为 b
2、B<A时
假设有一个 id 集合 A = { 1 , 2 , 3 , 4 , 5 , 5 , 5 , 5 , 5 , 5 , 6 , 7 }
此时 id 唯一的集合为 { 1 , 2 , 3 , 4 , 6 , 7 }
必须修改的 id 集合为 { 5 , 5 , 5 , 5 }
按照同样策略 让必须修改的 id 集合与 id 唯一的集合对应上 即将必须修改的 id 集合变为 { 1 , 2 , 3 , 4 } 但此时仍然发现 id 唯一的集合剩余的两个 id 为 { 6 , 7 }
我们需要让它们一致，所以需要修改其中一个
假设剩余 4 个呢？那我们需要修改 2 个
假设剩余 8 个呢？那我们需要修改 4 个
显然结论就是需要修改剩余 id 个数的一半，
即这种情况下答案是： b+(a-b/2)
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1e5+10;
unordered_map<int,int> all;
int n;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
while(n--){
int x;cin>>x;
all[x]++;
}
int a=0,b=0;
for(auto x:all){
// cout<<x.first<<" "<<x.second<<endl;
if(x.second==1) a++;
else if(x.second>2) b+=x.second-2;
}
if(b>=a) cout<<b<<endl;
else cout<<b+((a-b)/2)<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//多模拟几组案例可以发现 首先要把每个id记下数
//如果id小于2 说明肯定要改 或者等一个改成它
//如果id大于2 那么多出2的部分一定要改成其他的
// 1 2 2 2 2 2 3 4
// 22 3个2 分别改成 1 3 4 改三个数 这是多余部分（必须要改的部分） 恰好等于可能要改的部分的情况
// cost = 出现次数大于2的数量
// 1 2 2 2 3 4
// 22 1个2 改成1 3改成4 改两个数 这是多余部分（必须要改）的数 小于可能要改的数的情况
// cost = 出现次数大于2的数量 + 没被消耗完的 出现一次的数量 再除以2
// 1 1 2 2 2 2
// 11 22 多2个2 把22都改成33 改两个数 这是多余部分 大于 可能要改的部分的情况
//综上 先用值做下标计数 统计一下 出现一次的个数 以及 超过2部分的个数
// 若cnt2>=cnt1 则答案为cnt2
// 若cnt2<cnt1 则答案为 cnt2 + (cnt1-cnt2)/2
const int N=1e5+10;
int have[N];
int n;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
int maxv=0;
for(int i=0;i<n;i++){
int x;cin>>x;
have[x]++;
maxv=max(maxv,x);
}
int cnt1=0,cnt2=0;
for(int i=0;i<=maxv;i++){
if(have[i]==1)
cnt1++;
if(have[i]>2){
cnt2+=have[i]-2;
}
}
if(cnt2>=cnt1) cout<<cnt2<<endl;
else cout<<cnt2+((cnt1-cnt2)/2);
return 0;
}
💬 评论